package graph.impl;

import edu.princeton.cs.introcs.In;
import edu.princeton.cs.introcs.StdOut;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class StringGraphBFS {

	private Map<String,Boolean> visited = null;
	private StringGraph graph = null;
	private Queue<String> vertexQueue = null;
	
	public StringGraphBFS(StringGraph graph) {
		visited = new HashMap<String,Boolean>();
		this.graph = graph;
		vertexQueue = new LinkedList<String>();
	}

	public void bfs(String source){		
		vertexQueue.offer(source);
		fillQ(source);
		while(!vertexQueue.isEmpty()){
			String vertex = vertexQueue.remove();
			if(!visited.containsKey(vertex)){
				visited.put(vertex, Boolean.TRUE);
				fillQ(vertex);
			}			
		}	
	}
	private void fillQ(String source){
		Set<String> edges = graph.getEdges(source);
		for(String edge : edges){
			if(!vertexQueue.contains(edge))	{
				vertexQueue.offer(edge);		
			}
		}

	}
	public static void main(String[] args) {
		In in = new In(args[0]);
		StringGraph stringGraph = new StringGraph(in);
		StringGraphBFS bfs = new StringGraphBFS(stringGraph);
		bfs.bfs("ASH");
		if(bfs.visited.size() == stringGraph.vertexCount) {
			StdOut.println(bfs.visited);
		}
	}

}
